
class SuffixArray:
    def __init__(self,s):
        self.s = s
        sa,rank = self.build_suffix_array(s)
        self.sa = sa
        self.rank = rank
    def build_suffix_array(self,s):
        n = len(s)
        suffix_array = list(range(n))
        rank = [ord(c) for c in s]
        k = 1

        def key(x):
            return rank[x], rank[x + k] if x + k < n else -1

        while k < n:
            suffix_array.sort(key=key)
            tmp_rank = [0] * n
            for i in range(1, n):
                tmp_rank[suffix_array[i]] = tmp_rank[suffix_array[i - 1]]
                if key(suffix_array[i]) > key(suffix_array[i - 1]):
                    tmp_rank[suffix_array[i]] += 1
            rank = tmp_rank
            k *= 2

        return suffix_array,rank

    def build_lcp_array(self,s, suffix_array):
        n = len(s)
        rank = [0] * n
        lcp = [0] * n
        h = 0

        for i, suffix in enumerate(suffix_array):
            rank[suffix] = i

        for i in range(n):
            if rank[i] > 0:
                j = suffix_array[rank[i] - 1]
                while (i + h < n) and (j + h < n) and (s[i + h] == s[j + h]):
                    h += 1
                lcp[rank[i]] = h
                if h > 0:
                    h -= 1

        return lcp

    def lookup(self,t):
        pass
#         参考golang的suffix_array::lookup

